import java.util.Arrays;
import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[n], w = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        //定义状态表示，dp[i]为在装前i个物品时的最大价值，但是这样的状态表示是不行的，因为
        //这样无法知道当前情况下背包是否能够装下，所以这里我们更换状态表示为二维的dp表dp[i][j]表示在j背包容量下可以装的物品的最大价值
        //所以，状态转移方程为：根据最近的一个状态推出状态转移方程，最近的一个状态又可以分为将第i个物品装入背包，也可以不装，我们需要求的是两种情况的最大值dp[i][j] = max(dp[i-1][j],dp[i-1][j] + w[i])，不装的时候，dp[i-1][j]是存在的，但是装入第i个位置的物品的时候，我们还需要考虑到背包容量是否装的下的问题，也就是j-v[i]是否大于等于0
        int[][] dp = new int[n + 1][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }

        System.out.println(dp[n][V]);

        for (int i = 0; i <= n; i++) Arrays.fill(dp[i],0);
        for (int i = 1; i <= V; i++) dp[0][i] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i - 1] && dp[i - 1][j - v[i - 1]] != -1) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}
